package array;

/**
 * @author 孤雪唯方
 * @date 2025/05/10
 * @description 二分查找(有序数组)
 */
public class BinarySearch {
    /**
     * 二分查找
     *
     * @param arr    数组
     * @param toFind 需要查找的元素
     * @return int   找到返回数组下标,否则返回-1
     */
    public static int binarySearch(int[] arr,int toFind){
        int left = 0;//左边界
        int right = arr.length - 1;//右边界

        //循环查找,当左边界小于等于右边界时,继续查找
        while(left <= right){
            int mind = (left + right) / 2;//定义一个中间位置
            //被查找的数小于中间位置的数,则在左边查找
            if(toFind < arr[mind]){
                right = mind - 1;//更新右边界为中间位置的左边
            }else if(toFind > arr[mind]){
                //被查找的数大于中间位置的数,则在右边查找
                left = mind + 1;//更新左边界为中间位置的右边
            }else{
                //如果toFind等于中间位置的数,则说明找到了,并返回其数组下标
                return mind;
            }

        }
        //如果左边界大于右边界,这时循环结束,说明没有找到,返回-1
        return -1;
    }

    public static void main(String[] args) {
        //定义一个有序数组
        int[] arr = {1,2,3,4,5,6,7,8,9};
        //运行二分查找函数,查找元素5,并将返回结果存储在index变量中
        int index = binarySearch(arr, 5);
        //根据index的值判断是否找到了元素
        if(-1 == index){
            System.out.println("没有找到");
        }else {
            System.out.println("找到了,下标为" + index + ",值为" + arr[index]);
        }
        System.out.println(binarySearch(arr, 0));
    }

}
